package algorithm.middle;

import java.util.ArrayList;


/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CountTriplets1442
 * @description: 给你一个整数数组 arr 。
 *
 * 现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
 *
 * a 和 b 定义如下：
 *
 * a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
 * b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
 * 注意：^ 表示 按位异或 操作。
 *
 * 请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/5/1815:17
 * @since V1.0
 */
public class CountTriplets1442 {

    /** 异或运算 位运算 前缀和
     * 即找所有 [i,k]所有异或和相加为0的区间，然后每个区间求出ijk的排列组合个数
     */
    public int countTriplets(int[] arr) {
        int count = 0;
        //先求出[0,index]的暂存数组
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        ArrayList<int[]> list = new ArrayList<>();
        for (int i=1;i<arr.length;i++){
            dp[i] = dp[i-1]^arr[i];
            //dp[i]=0 -> [0,i]
            //if (dp[i]==0) list.add(new int[]{0,i});
            if (dp[i]==0) count+=i;
        }
        //再找到[i,k]为0的区间 即 dp[i-1] ^ dp[j] = 0;
        for (int i=1;i<dp.length-1;i++){
            for (int j=i+1;j<dp.length;j++){
                if ((dp[i-1]^dp[j])==0){
//                    list.add(new int[]{i,j});
                    count +=j-i;
                }
            }
        }
//        list.forEach((o) -> System.out.println(Arrays.toString(o)));
        //处理lsit中的所有搭配
//        int count = 0;
//        for (int[] a:list){
//            count = count + a[1]-a[0];
//        }
        return count;
    }

    public static void main(String[] args) {
        int i = new CountTriplets1442().countTriplets(new int[]{2, 3, 1, 6, 7});
        System.out.println(i);
    }
}
